/**
 * 
 */
package array;

import java.util.Arrays;

/**
 * @author Michael
 *
 */
public class FindClosestNumber {

	public static int search(int[] a, int key) {
		assert (a != null && a.length > 0);

		Arrays.sort(a);
		int left = 0;
		int right = a.length - 1;
		if (key <= a[left])
			return a[left];
		if (key >= a[right])
			return a[right];
		
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (key == a[mid]) {
				return a[mid];
			}
			else if (key < a[mid]) {
				right = mid - 1;
			}
			else {
				left = mid + 1;
			}
		}
		
		return Math.abs(key - a[left]) < Math.abs(key - a[right]) ? a[right] : a[left];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { -5, -3, 1, 3, 7, 8, 8, 8, 9 };
		System.out.println(search(a, -4));
		//System.out.println(bs(a, 11));

	}

	/**
	 * 
	 */
	public FindClosestNumber() {
		// TODO Auto-generated constructor stub
	}
}
